package com.itheima.leetcode.od.b.backtracking;

import java.util.*;

/**
 * (B卷,200分)- 人气最高的店铺（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 某购物城有m个商铺，现决定举办一场活动选出人气最高店铺。
 * <p>
 * 活动共有n位市民参与，每位市民只能投一票，但1号店铺如果给该市民发放 q 元的购物补贴，该市民会改为投1号店铺。
 * <p>
 * 请计算1号店铺需要最少发放多少元购物补贴才能成为人气最高店铺（即获得的票数要大于其他店铺），如果1号店铺本身就是票数最高店铺，返回0。
 * <p>
 * 输入描述
 * <p>
 * 第一行为小写逗号分割的两个整数n，m，其中：
 * <p>
 * 第一个整数n表示参与的市民总数
 * 第二个整数m代表店铺总数
 * 1 ≤ n,m ≤ 3000
 * 第2到n+1行，每行为小写逗号分割的两个整数p，q，表示市民的意向投票情况，其中每行的：
 * <p>
 * 第一个整数p表示该市民意向投票给p号店铺
 * 第二个整数q表示其改投1号店铺所需给予的q元购物补贴
 * 1 ≤ p ≤ m
 * 1 ≤ g ≤ 10^9
 * 不考虑输入的格式问题
 * <p>
 * 输出描述
 * <p>
 * 1号店铺需要最少发放购物补贴金额
 * <p>
 * 用例
 * <p>
 * 输入	5,5
 * 2,10
 * 3,20
 * 4,30
 * 5,40
 * 5,90
 * 输出	50
 * 说明
 * 有5个人参与，共5个店铺。
 * 如果选择发放 10元+20元+30元=60元 的补贴来抢2,3.4号店铺的票，总共发放了60元补贴（5号店铺有2票，1号店铺要3票才能胜出）
 * <p>
 * 如果选择发放 10元+40元=50元 的补贴来抢2,5号店铺的票，总共发放了50元补贴（抢了5号店铺的票后，现在1号店铺只要2票就能胜出）
 * <p>
 * 所以最少发放50元补贴
 * <p>
 * 输入	5,5
 * 2,10
 * 3,20
 * 4,30
 * 5,80
 * 5,90
 * 输出	60
 * 说明
 * 有5个人参与，共5个店铺。
 * <p>
 * 如果选择发放 10元+20元+30元=60元 的补贴来抢2,3,4号店铺的票，总共发放了60元补贴(5号店铺有2票，1号店铺要3票才能胜出)
 * <p>
 * 如果选择发放 10元+80元=90元 的补贴来抢2,5号店铺的票，总共发放了90元补贴(抢了5号店铺的票后，现在1号店铺只要2票就能胜出)
 * <p>
 * 所以最少发放60元补贴
 * <p>
 * 题目解析
 * <p>
 * 本题就是
 * <p>
 * 51nod - 1494 选举拉票（Java & JS & Python）_伏城之外的博客-CSDN博客
 * <p>
 * 的换皮题，具体解析请看该博客的。
 */
public class MostPopularStore {
    public static void main(String[] args) {
        /*//输入
        Scanner in = new Scanner(System.in);
        int[] params = Arrays.stream(in.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int n = params[0];
        int m = params[1];
        // 初始化商店和投票人
        List<int[]> peoples = new ArrayList<>();
        Map<Integer, Integer> shop_info = new HashMap<>();
        shop_info.put(1, 0);
        for(int i=0; i<n; i++){
            int[] nums = Arrays.stream(in.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
            if(nums[0] != 1){
                peoples.add(new int[]{nums[0], nums[1]});
            }
            shop_info.put(nums[0], shop_info.getOrDefault(nums[0], 0) + 1);
        }*/

        // 市民数量
        int n = 5;
        // 店铺数量
        int m = 5;
        int[][] arr = Arrays.stream("2,10 3,20 4,30 5,40 5,90".split(" "))
                .map(s -> Arrays.stream(s.split(","))
                        .mapToInt(Integer::valueOf)
                        .toArray())
                .toArray(int[][]::new);
        // 初始化商店和投票人
        List<int[]> peoples = new ArrayList<>();
        Map<Integer, Integer> shop_info = new HashMap<>();
        shop_info.put(1, 0);
        for (int i = 0; i < arr.length; i++) {
            int[] nums = arr[i];
            if (nums[0] != 1) {
                peoples.add(new int[]{nums[0], nums[1]});
            }
            shop_info.put(nums[0], shop_info.getOrDefault(nums[0], 0) + 1);
        }

        backfill(peoples, new LinkedList<>(), 0, shop_info);
        System.out.println(result);
    }

    public static int money;
    public static int result = Integer.MAX_VALUE;

    /**
     * 回溯求解
     *
     * @param peoples
     * @param change_peoples
     * @param index
     * @param shop_info
     */
    public static void backfill(List<int[]> peoples, LinkedList<int[]> change_peoples, int index, Map<Integer, Integer> shop_info) {
        // 判断此时一号店铺是否是第一名,且所需要的钱最少
        if (check(change_peoples, shop_info)) {
            result = Math.min(result, money);
            return;
        }
        // 组合求解
        for (int i = index; i < peoples.size(); i++) {
            change_peoples.push(peoples.get(i));
            backfill(peoples, change_peoples, i + 1, shop_info);
            change_peoples.pop();
        }
    }

    /**
     * 回溯return条件
     *
     * @param change_peoples
     * @param shop_info
     * @return
     */
    public static boolean check(LinkedList<int[]> change_peoples, Map<Integer, Integer> shop_info) {
        Map<Integer, Integer> new_shop_info = new HashMap<>(shop_info);
        money = 0;
        for (int[] ints : change_peoples) {
            int shop_id = ints[0];
            money += ints[1];
            // 人气调换
            new_shop_info.put(shop_id, new_shop_info.get(shop_id) - 1);
            new_shop_info.put(1, new_shop_info.get(1) + 1);
        }

        // map如何排序（转List<Entry>）
        List<Map.Entry<Integer, Integer>> shop_list = new ArrayList<>(new_shop_info.entrySet());
        // 降序排序(大顶堆)
        shop_list.sort((a, b) -> b.getValue() - a.getValue());

        // 人气第一的店铺
        int top1_shop_id = shop_list.get(0).getKey();
        if (top1_shop_id == 1 && (shop_list.size() == 1 || shop_list.get(0).getValue() > shop_list.get(1).getValue())) {
            return true;
        }

        return false;
    }
}
